//160 Intersection of Two Linked Lists
/*
给定两个链表，判断它们是否相交于一点，并求这个相交节点
输入是两条链表，输出是一个节点。如无相交节点，则返回一个空节点

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2


*/
/*
哈希表法：遍历链表 A 并将每个结点的地址/引用存储在哈希表中。然后检查链表 B 中的每一个结点 bib_ibi​ 是否在哈希表中。若在，则 bib_ibi​ 为相交结点


*/
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
	unordered_map<Listnode> hashtable; //
	
	ListNode *A = headA;
	while(A != null)
	{
		hashtable.add(A);
		A = A.nest;
	}

	ListNode *B = headB;
	while(B != null)
	{
		if(hashtable.contains(B))
		{
			return B;
		}
	}

	return 0;
}

//双指针
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
	ListNode *l1 = headA, *l2 = headB;
	while (l1 != l2)
	{
		l1 = l1 ? l1->next : headB;
		l2 = l2 ? l2->next : headA;
	}
	return l1;
}